package com.yx.study.leet.daily;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname diffWaysToCompute241
 * @Date 2022/07/01 14:16
 * @Author by yx
 * @Description :
 */
public class diffWaysToCompute241 {
    int ADD = -1;
    int SUB = -2;
    int MUL = -3;

    List<Integer> ops = new ArrayList<>();
    List<Integer>[][] dp;

    List<Integer> dfs(int l, int r) {
        if (dp[l][r].isEmpty() == false) {
            return dp[l][r];
        }

        if (l == r) {
            dp[l][r].add(ops.get(l));
        } else {
            for (int i = l; i < r; i += 2) {
                int x = ops.get(i + 1);
                List<Integer> left = dfs(l, i);
                List<Integer> right = dfs(i + 2, r);
                for (int a : left) {
                    for (int b : right) {
                        if (x == ADD) {
                            dp[l][r].add(a + b);
                        } else if (x == SUB) {
                            dp[l][r].add(a - b);
                        } else {
                            dp[l][r].add(a * b);
                        }
                    }
                }
            }
        }

        return dp[l][r];
    }

    public List<Integer> diffWaysToCompute(String expression) {
        int n = expression.length();
        int i = 0;
        while (i < n) {
            if (Character.isDigit(expression.charAt(i)) == false) {
                if (expression.charAt(i) == '+') {
                    ops.add(ADD);
                } else if (expression.charAt(i) == '-') {
                    ops.add(SUB);
                } else {
                    ops.add(MUL);
                }
                i++;
            } else {
                int x = 0;
                while (i < n && Character.isDigit(expression.charAt(i)) == true) {
                    x = x * 10 + expression.charAt(i) - '0';
                    i++;
                }
                ops.add(x);
            }
        }

        int on = ops.size();
        dp = new List[on][on];
        for (int l = 0; l < on; l++) {
            for (int r = 0; r < on; r++) {
                dp[l][r] = new ArrayList<>();
            }
        }

        List<Integer> res = dfs(0, on - 1);
        return res;
    }

}
